package cn.edu.xjtu.carlWay.array.minimumSizeSubarraySum;

/**
 * 209. 长度最小的子数组
 * <p>
 * 给定一个含有n个正整数的数组和一个正整数 target 。
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = {2, 3, 1, 2, 4, 3};
        System.out.println(solution.minSubArrayLen(7, nums));
    }

    public int minSubArrayLen(int target, int[] nums) {
        int left = 0;
        int right = 1;
        int length = nums.length;
        int sum = nums[0];
        int minLength = 0;
        while (left < length || right < length) {
            if (sum >= target) {
                if (minLength == 0 || right - left < minLength) {
                    minLength = right - left;
                }
                sum -= nums[left];
                left++;
            } else {
                if (right == length) {
                    // 如果right等于length了,仍然没有target大,那么就无需移动left了
                    break;
                } else {
                    sum += nums[right];
                    right++;
                }
            }
        }
        return minLength;
    }
}
